  IOI. 8. (Colier). Se considera un colier format din n(n100) margele, care
pot avea numai culorile rosu (o), alb (&) sau albastru (*) aranjate ntr-un
mod arbitrar. In continuare apar doua exemple pentru n=29 n care sunt
precizate pozitiile primeia si celei de-a doua margele:
              1 2                             1 2
          o * * o                         * o o *
        o         *                     *         *
      o             o                 *             o
    o                 o             &                 o
  *                     o         &                     &
*                         *      o                       o
*                         *      *                       *
*                         *      o                       *
  o                     o         *                     o
    *                 o             o                 o
       *            o                 o             o
         o        o                     o         *
           o * o                           o o &
In fisierul de intrare culorile margelelor sunt indicate prin b (albastru),
r (rosu) si w (alb). Astfel, colierul din prima figura de mai sus va fi
reprezentat prin sirul
              brbrrrbbbrrrrrbrrbbrbbbbrrrrb.
   Colierul se rupe ntre doua margele consecutive. Plecnd de la ambele
capete spre centru se considera numarul maxim de margele consecutive de
aceeasi culoare; fie M suma lor. La numarare, un caz particular l
constituie margelele albe, care pot fi recolorate n rosu sau albastru astfel
nct M sa fie maxim.
   Se cer valoarea maxima a lui M si numerele de ordine ale margelelor
consecutive ntre care se face taietura. Se cere o singura solutie pentru
locul de taietura.
    Fisierul de intrare este de tip text si contine cte o configuratie
(colier) pe fiecare linie. Un exemplu este urmatorul:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb
  Rezultatele vor fi scrise ntr-un fisier de solutii. Rezultatele pentru
configuratii diferite vor fi separate ntre ele printr-o linie alba. Un
exemplu de fisier corect de iesire pentru fisierul de intrare de mai sus
este urmatorul:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
8 between 9 and 10

bbwbrrrwbrbrrrrrb
10 between 16 and 17
==============================
Solutia 1 (Mihai Stroe):
    Aceasta este o problema de atentie. Consideram ca doua margele sunt de
  aceeasi culoare si daca cel putin una este alba.
  Una din metodele de rezolvare este:
  - se calculeaza pentru fiecare componenta a colierului numarul de margele
  de aceeasi culoare din stinga si apoi din dreapta (a[i],b[i]);
  - se calculeaza numarul cerut pentru fiecare posibila taiere, prin adunarea
  lui a[i] cu b[i+1]; aici intervin doua cazuri limita:
                      - suma depaseste n, caz in care suma:=n;
                      - i=n, deci taiere intre margelele n si 1.
    Din numerele calculate se obtine maximul; taierea corespunzatoare se scrie
  in fisierul de iesire.
    Complexitatea este n^2, convenabila pentru n<=100; problema se poate
  rezolva si liniar, folosind o metoda rapida pentru obtinerea vectorilor
  a si b.

var fi,fo:text;
    c:array[-100..200]of char;
    a,b:array[-100..200]of byte;
    i,j,k,l,m,n:integer;
    s:string;

procedure readdata;
begin
  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);
  fillchar(c,sizeof(c),0);
  n:=0;
  while not eoln(fi) do
    begin
      inc(n);
      read(fi,c[n]);
      write(fo,c[n]);
    end;
  readln(fi);
  writeln(fo);
end;

procedure calcul;
begin
  a[0]:=1;
  for i:=1 to n do
      if (c[i]='w')or(c[i]=c[i-1]) then a[i]:=a[i-1]+1
                                   else a[i]:=1;
end;
procedure solve;
begin
  for i:=1 to n do
      begin
        c[n+i]:=c[i];
        c[1-i]:=c[n-i+1];
      end;
  for i:=0 to n do
      begin
        j:=i;
        while((c[j]=c[i])or(c[j]='w'))and(j<n*2) do inc(j);
        b[i]:=j-i;
        j:=i;
        while((c[j]=c[i])or(c[j]='w'))and(j>-n) do dec(j);
        a[i]:=i-j;
      end;
  m:=0;l:=0;
  for i:=0 to n do
      if a[i]+b[i+1]>m then
         begin
           m:=a[i]+b[i+1];
           l:=i;
         end;
  if m>n then m:=n;
  if l=0 then writeln(fo,m,' between ',n,' and ',1)
     else writeln(fo,m,' between ',l,' and ',l+1);
  writeln(fo);
end;

begin
  write('Type input file name ');
  readln(s);
  assign(fi,s);
  write('Type output file name ');
  readln(s);
  assign(fo,s);
  reset(fi);
  rewrite(fo);
  while not eof(fi) do
    begin
      readdata;
      solve;
    end;
  close(fi);
  close(fo);
end.
---------------------------------------
Solutia 2 ( Mihai Badoiu):
Grad de dificultate:mediu
Tehnica folosita:Programare dinamica O(n)
Comentarii: Aceasta este o problema foarte interesanta. Cu metoda
bruta se poate scoate O(n*n) care este de ajuns, iar cu programare
dinamica O(n).
var
        fo:text;
        s:string;
        rs,rd:array[1..100] of byte;

procedure calcul;
var
        stare:char;
        k,i,j,n,nw:integer;
begin
        n:=0;
        nw:=0;
        for k:=1 to 2 do
        for i:=1 to length(s) do
        begin
                if (s[i]='w') then
                begin
                        n:=n+1;
                        nw:=nw+1;
                        end
                else
                begin
                        if (s[i]=stare) then
                                n:=n+1
                        else
                        begin
                                n:=nw+1;
                                end;
                        stare:=s[i];
                        nw:=0;
                        end;
                if n>rs[i] then
                        rs[i]:=n;
                end;
        n:=0;
        nw:=0;
        for k:=1 to 2 do
        for i:=length(s) downto 1 do
        begin
                if (s[i]='w') then
                begin
                        n:=n+1;
                        nw:=nw+1;
                        end
                else
                begin
                        if (s[i]=stare) then
                                n:=n+1
                        else
                        begin
                                n:=nw+1;
                                end;
                        stare:=s[i];
                        nw:=0;
                        end;
                if n>rd[i] then
                        rd[i]:=n;
                end;
        j:=1;
        for i:=1 to length(s)-1 do
        begin
                if rs[i]+rd[i+1]>rs[j]+rd[j+1] then
                        j:=i;
                end;
        writeln(s);
        if rs[length(s)]+rd[1]>length(s) then
        begin
                writeln(length(s),' between ',length(s),' and 1');
                end
        else
        if rs[length(s)]+rd[1]>j then
        begin
                writeln(rs[length(s)]+rd[1],' between ',length(s),' and 1');
                end
        else
        begin
                writeln(rs[j]+rd[j+1],' between ',j,' and ',j+1);
                end;
end;

procedure init;
var
        i:integer;
begin
        for i:=1 to 100 do
        begin
                rs[i]:=0;
                rd[i]:=0;
                end;
end;

procedure load;
var
        nume:string;
        f:text;
begin
        write('fis int. = ');
        readln(nume);
        assign(f,nume);
        reset(f);
        write('fis out = ');
        readln(nume);
        assign(fo,nume);
        rewrite(fo);
        while not seekeof(f) do
        begin
                readln(f,s);
                init;
                calcul;
                end;
        close(fo);
        close(f);
end;

begin
        load;
end.
----------------------------------
Solutia 3 (Peter Szolt)
  Rezolvarea se bazeaza pe idea ca taierea trebuie facuta intre doua margele
de culori diferite. Parcurg sirul de la inceputul unor sir de margele de ace-
iasi culor, pana cand nu ajung de a doua ora la sfarsitul acestei secvente.

program IOI8;
const
  Rezultat='rezultat.out';
var
 s:string;
 f,g:text;
procedure Calc;
var
  L:byte;
  O,I:byte;
  M,V:byte;
  C:byte;
  B,R,T,W,EW,CC,Out:byte;
begin
  L:=byte(S[0]);
  b:=0;r:=0;t:=0;
  for i:=1 to l do  begin
    if s[i]='b' then begin b:=1;if (t=0) {and (r=1)} then t:=i;end;
    if s[i]='r' then begin r:=1;if (t=0) {and (b=1)} then t:=i;end;
  end;
  if (r=0) or (b=0) then begin
    writeln(g,l,' between ',l,' and 1');
    exit;
  end;
  m:=0;
  i:=t;
  o:=0;
  t:=0;
  ew:=0;
  repeat
    c:=i;
    w:=0;
    cc:=0;
    repeat
      if s[i]='w' then inc(w) else w:=0;
      inc(i);
      inc(cc);
      if i>L then i:=1;
    until ((s[i]<>s[c]) and (s[i]<>'w'));

    if cc+o>m then begin
      m:=cc+o;
      if m>l then m:=l;
      v:=c;
    end;
    o:=cc+ew;
    ew:=w;
    inc(out);
    if (t=0) and (out=2) then begin t:=i;out:=0;end;
  until (out<>0) and (t=i);
  writeln(g,m,' between ',(v+l-1) mod l,' and ',v);
end;

begin
  write('Fisierul de intrare:');
  readln(s);
  assign(f,s);
  assign(g,Rezultat);
  reset(f);
  rewrite(g);
  while not eof(f) do begin
    readln(f,s);
    writeln(g,s);
    calc;
    writeln(g);
  end;
  close(g);
  close(f);
end.
-----------------------------
Solutia 4 (Catalin Francu)
program Colier;
const NMax=100;
var InName,OutName:String;
    S:String[NMax];
    N:Byte absolute S;
    Left,Right:array[1..NMax] of Integer;

procedure FindLeftLimits;
var i,j,Red,Blue:Integer;
begin
  Red:=0;Blue:=0;
  for i:=1 to 2 do
    for j:=1 to N do
      begin
        case S[j] of
          'r':begin
                Inc(Blue);
                Red:=0;
              end;
          'b':begin
                Inc(Red);
                Blue:=0;
              end;
          'w':begin
                Inc(Red);
                Inc(Blue);
              end;
        end; {case}
        if Blue>Red then Left[j]:=Blue else Left[j]:=Red;
      end;
end;

procedure FindRightLimits;
var i,j,Red,Blue:Integer;
begin
  Red:=0;Blue:=0;
  for i:=1 to 2 do
    for j:=N downto 1 do
      begin
        case S[j] of
          'r':begin
                Inc(Blue);
                Red:=0;
              end;
          'b':begin
                Inc(Red);
                Blue:=0;
              end;
          'w':begin
                Inc(Red);
                Inc(Blue);
              end;
        end; {case}
        if Blue>Red then Right[j]:=Blue else Right[j]:=Red;
      end;
end;

procedure FindBest;
var i,k:Integer;
begin
  WriteLn(S);
  k:=1;
  for i:=2 to N do
    if Left[i]+Right[i+1]>Left[k]+Right[k+1] then k:=i;
  if Left[K]+Right[K]>N
    then WriteLn(N,' between ',k,' and ',k+1)
    else WriteLn(Left[k]+Right[k+1],' between ',k,' and ',k+1);
  WriteLn;
end;

begin
  Write('Numele fisierului de intrare: ');ReadLn(InName);
  Write('Numele fisierului de iesire: ');ReadLn(OutName);
  Assign(Input,InName);Reset(Input);
  Assign(Output,OutName);Rewrite(Output);
  while not Eof do
    begin
      ReadLn(S);
      FindLeftLimits;
      FindRightLimits;
      FindBest;
    end;
  Close(Input);Close(Output);
end.
------------------------------------------------
Solutia mea:
Algoritm:
Pentru a facilita calculele, vom nota culoarea rou cu 0, alb cu 1 i albastru cu 2.
Algoritmul este iterativ; caut[ din toate situaiile posibile acea t[ietur[ s care duce la maximizarea
valorii lui M.
              Am introdus trei subalgoritmi:
numar(colier,k) - calculeaz[ num[rul k de m[rgele de aceeai culoare situate pe colier, parcurs
                                     spre dreapta;
revers(colier) - consider[ vectorul colier scris n ordine invers[;
ciclic(colier) - efectueaz[ permutarea ciclic[ a m[rgelelor colierului; este echivalent cu                                       aciunea de t[iere a colierului dup[ m[rgica urm[toare.

1. M:=1; s:=0;
2. pentru i:=1,n-1
     2.1. numar(colier,p);
     2.2. numar(revers(colier),q);
     2.3. Dac[ M<p+q atunci M:=p+q, s:=i;
     2.4. Dac[ M=n atunci salt la 3;
     2.5. colier:=ciclic(colier);
3. Scrie M,(s,s+1).
numar(colier,k)
1. a:=colier(1); i:=2;
2. Dac[ ac1 atunci
     2.1. cat timp (|colier(i)-a|1) i (in)
                  i:=i+1;
     2.2. k:=i-1; Revenire;
3. Dac[ |colier(i)-a|=1 atunci a:=colier(i);
4. i:=i+1;
5. Dac[ (a=1) i (in) atunci salt la 3
                       altfel salt la 2.1.

Program:
uses crt;
var s:string[100];
    suma1,suma2,i,sumamax,taietura,solutie:integer;
begin
clrscr;
assign(input,'input.io8');
assign(output,'output.io8');
rewrite(output);
reset(input);
while not eof(input) do
      begin
      readln(input,s);
      taietura:=1;
      sumamax:=0;
      solutie:=taietura;
      while taietura<=length(s) do
            begin
            i:=taietura;
            suma1:=0;
            while ((s[i]='w') or (s[i]=s[taietura])) and not((suma1<>0) and
(i=taietura)) do
                  begin
                  dec(i);
                  inc(suma1);
                  if i<1 then i:=length(s);
                  end;
            suma2:=0;
            i:=taietura+1;
            while ((s[i]='w') or (s[i]=s[taietura+1])) and not((suma2<>0) and
(i=taietura+1)) do
                  begin
                  inc(i);
                  inc(suma2);
                  if i>length(s) then i:=1;
                  end;
            if suma1+suma2>sumamax then
               begin
               sumamax:=suma1+suma2;
               solutie:=taietura;
               end;
            inc(taietura);
            end;
      writeln(output,s);
      writeln(output,sumamax,' between ',solutie,' and ',solutie+1);
      writeln(output);
      end;
end.
-----------------------------------------------
